题面

解题思路

某种叫作 $wqs$ （忘情水）二分的神奇算法，具体的算法内容等详见学习笔记

分析

$Kruskal$ 算法只能求解最小生成树，但是由于要求的白边数是一定的，这将导致最后的生成树并不是最小生成树

于是考虑怎么消除白边的影响，不难想到，如果白边的边权越小，最后求出的最小生成树中的白边数肯定越多，于是就可以二分白边改变的值，表示白边的边权减小 $mid$ ，然后再跑一遍生成树，如果生成树中白边数大于 $K$ 说明修改的值过大，则将右边界减小，否则将左边界增大

这样满足最后得出的答案，一定是满足有 $K$ 条白边的情况，因为题目中保证有解，且如果不满足 $K$ 条边的情况，二分都会将对左或右边界做出调整

最后答案即为求出最小生成树的边权加上 $K \times$ 白边改变的值

warning

1、由于可能存在白边和黑边的边权一样的情况，所以在 $Kruskal$ 对边进行排序时，要把边权作为第一关键字，颜色作为第二关键字

2、排序可以用归并排序优化（白边边权改变后按边权排序的排名并没有变化

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define inf 0x7f7f7f7f
#define M 100007
#define N 50007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
struct node{
    int x,y,w,c;
}b[M],p[M];
int n,m,k,res,sum,ans,f[N],block,l,r,mid;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline bool cmp(rgt node a,rgt node b) {return (a.w!=b.w)?a.w<b.w:a.c<b.c;}//排序
inline int get(rint x) {return (f[x]!=x)?f[x]=get(f[x]):x;}
inline int Kruskal(rint k) {
    rint i,fx,fy;
    for(i=1;i<=m;i++) {
        b[i]=p[i];
        if(!p[i].c) b[i].w-=k;//改变白边的边权
    }sort(b+1,b+1+m,cmp),block=sum=0;//可以用归并复杂度较优
    for(i=1;i<=n;i++) f[i]=i;//初始化并查集
    for(i=1;i<=m;i++) {
        fx=get(b[i].x),fy=get(b[i].y);
        if(fx==fy) continue;
        f[fy]=fx;
        sum+=!b[i].c;//记录白边数
        if(block==n-1) break;
    }
    return sum;
}
inline void solve(rint k) {//最后用来求最小生成树用
    rint i,fx,fy;
    for(i=1;i<=m;i++) {
        b[i]=p[i];
        if(!p[i].c) b[i].w-=k;
    }sort(b+1,b+1+m,cmp),block=ans=0;
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++) {
        fx=get(b[i].x),fy=get(b[i].y);
        if(fx==fy) continue;
        f[fy]=fx;
        ans+=b[i].w;
        if(block==n-1) break;
    }
}
int main()
{
    int i;
    n=read(),m=read(),k=read();
    for(i=1;i<=m;i++)
        p[i].x=read()+1,p[i].y=read()+1,
        cmax(r,p[i].w=read()),p[i].c=read();
    l=-r;//可以增大，可以减小
    while(l<=r) {//二分白边的改变值
        mid=(l+r)>>1;
        if(Kruskal(mid)>=k)//满足条件说明还可以将改变值边的更小
            res=mid,r=mid-1;
        else l=mid+1;
    }
    solve(res);
    printf("%d",ans+res*k);//答案要加上边数×改变的值
    return 0;
}

devil.